﻿using System;

class MaximumSubMatrixSum
{
    static int[,] bestMatrix;
    static int bestSum;
    static int[,] array = 
    {
        { 1, 5, 9, 13 },
        { 2, 6, 10, 14 },
        { 3, 7, 11, 15 },
        { 1, 5, 9, 13 },
        { 4, 8, 12, 16 },
    };

    static void Main()
    {
        for (int i = 0; i <= array.GetLength(0) - 3; i++)
        {
            for (int j = 0; j <= array.GetLength(1) - 3; j++)
            {
                MaximumSum(i, j);
            }
        }
        Console.WriteLine("The best matrix is:");
        Print(bestMatrix);
        Console.WriteLine("The best sum is: {0}", bestSum);
    }

    private static void MaximumSum(int startX, int startY)
    {
        int[,] candidateMatrix = new int[3, 3];
        int candidateSum = 0;

        for (int i = startX; i < startX + 3; i++)
        {
            for (int j = startY; j < startY + 3; j++)
            {
                candidateMatrix[i - startX, j - startY] = array[i, j];
                candidateSum += array[i, j];
            }
        }
        if (candidateSum > bestSum)
        {
            bestMatrix = candidateMatrix;
            bestSum = candidateSum;
        }
    }

    static void Print(int[,] array)
    {
        for (int i = 0; i < array.GetLength(0); i++)
        {
            for (int j = 0; j < array.GetLength(1); j++)
            {
                Console.Write(" " + array[i, j]);
            }
            Console.WriteLine();
        }
    }
}